package com.ly.algorithm.leetcode.binarysearch;

/**
 * @Classname Interview1003
 * @Description
 *
 * 示例1:
 *
 *  输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
 *  输出: 8（元素5在该数组中的索引）
 * 示例2:
 *
 *  输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
 *  输出：-1 （没有找到）
 *
 * @Date 2020/12/20 20:18
 * @Author 冷心影翼
 */
public class Interview1003 {

	public static void main(String[] args) {
		Solution1003 solution1003 = new Solution1003();
		int search = solution1003.search(new int[]{15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14}, 5);
		System.out.println(search);
	}
}

class Solution1003 {
	public int search(int[] arr, int target) {
		if(arr.length == 0) return -1;
		int left = 0, right = arr.length-1;
		while(left <= right){
			int mid = (left+right) >> 1;
			//左边有序
			if(arr[left] < arr[mid]){
				//目标值在左边
				if(arr[left] <= target && target <= arr[mid])
					right = mid;
				else
					left = mid+1;
			}
			//右边有序
			else if(arr[left] > arr[mid]){
				//目标值在右边
				if(arr[mid] <= target && target <= arr[right] && arr[left] > arr[right])
					left = mid;
				else
					right = mid-1;
			}
			//如果左值等于中值，可能是已经找到了目标，也可能是遇到了重复值
			else if(arr[left] == arr[mid]){
				//如果左值不等于目标，说明还没找到，需要逐一清理重复值。
				if(arr[left] != target)
					left++;
				else
					return left;
			}
		}
		return -1;
	}
}
